package 剑指Offer1;

public class _06重建二叉树 {public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode(int x) { val = x; }
   }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder,0,preorder.length-1,
                    inorder,0,inorder.length-1);
    }

    private TreeNode build(int[] preorder,int preStart,int preEnd,
                           int[] inorder,int inStart,int inEnd){
       if(preStart>preEnd || inStart>inEnd) return null;
       int rootVal = preorder[preStart];
       int index = -1;
       for(int i=inStart;i<=inEnd;++i){
          if(rootVal == inorder[i]){
               index = i;
               break;
          }
       }
       int leftSize = index - inStart;
       TreeNode root = new TreeNode(rootVal);
       root.left = build(preorder,preStart+1,preStart+leftSize,
                        inorder,inStart,index-1);
       root.right = build(preorder,preStart+leftSize+1,preEnd,
                        inorder,index+1,inEnd);
       return root;
    }
}
